
public class Permutation {
	
	public static void permute(String str){
		int length = str.length();
		
		boolean[] used = new boolean[length];
		
		StringBuffer output = new StringBuffer();
		
		permutation(str, length, output, used, 0);
	}
	
	public static void permutation(String str, int length, StringBuffer output, boolean[] used, int position){
		//base case
		if(position == length){
			System.out.println(output.toString());
			return;
		}
		else{
			for(int i = 0; i < length; i++){
				//skip already used characters
				if(used[i]){
					continue;
				}
				
				//add fixed character to output and mark it as true
				output.append(str.charAt(i));
				used[i] = true;
				
				//permute over remaining character starting at position+1
				permutation(str, length, output, used, position+1);
				
				//remove fixed character from output, and unmark it
				
				output.deleteCharAt(output.length()-1);
				used[i] = false;
			}
		}
	}
	
	
	
	/*************************************************************************
	 * 
	 *  Execution:    java Permutations N k
	 *  
	 *  Generate permutations by transposing adjacent elements using the
	 *  Johnson-Trotter algorithm.
	 *
	 *  This program is a Java version based on the program SJT.c
	 *  writen by Frank Ruskey.
	 *  
	 *     http://theory.cs.uvic.ca/inf/perm/PermInfo.html
	 * 
	 *  % java JohnsonTrotter 3
	 *  012   (2 1)
	 *  021   (1 0)
	 *  201   (2 1)
	 *  210   (0 1)
	 *  120   (1 2)
	 *  102   (0 1)
	 *
	 *************************************************************************/
	
	
	 public static void perm(int N) {
	        int[] p   = new int[N];     // permutation
	        int[] pi  = new int[N];     // inverse permutation
	        int[] dir = new int[N];     // direction = +1 or -1
	        for (int i = 0; i < N; i++) {
	            dir[i] = -1;
	            p[i]  = i;
	            pi[i] = i;
	        }
	        perm(0, p, pi, dir);
	        System.out.printf("   (0 1)\n");
	    }

	    public static void perm(int n, int[] p, int[] pi, int[] dir) { 

	        // base case - print out permutation
	        if (n >= p.length) {
	            for (int i = 0; i < p.length; i++)
	                System.out.print(p[i]);
	            return;
	        }

	        perm(n+1, p, pi, dir);
	        for (int i = 0; i <= n-1; i++) {

	            // swap 
	            System.out.printf("   (%d %d)\n", pi[n], pi[n] + dir[n]);
	            int z = p[pi[n] + dir[n]];
	            p[pi[n]] = z;
	            p[pi[n] + dir[n]] = n;
	            pi[z] = pi[n];
	            pi[n] = pi[n] + dir[n];  

	            perm(n+1, p, pi, dir); 
	        }
	        dir[n] = -dir[n];
	    }
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
//		permute("abcdefghijklmnopqrstuvwxyz");
		long startTime = System.currentTimeMillis();
		 perm(3);
		 
		 // Get the Java runtime
		    Runtime runtime = Runtime.getRuntime();
		    // Run the garbage collector
		    runtime.gc();
		    // Calculate the used memory
		    long memory = runtime.totalMemory() - runtime.freeMemory();
		    System.out.println("Used memory is bytes: " + memory);
		 long stopTime = System.currentTimeMillis();
		 long elapsedTime = stopTime - startTime;
		    System.out.println(elapsedTime);
	}

}
